package main
import(
	"github.com/cheekybits/genny/generic"
	"sync"
	"fmt"
)
/*
------------------------------------------------
                     ---[ 1
              ---[ 2
                     ---[ 3
       ---[ 4
                     ---[ 5
              ---[ 6
                     ---[ 7
---[ 8
              ---[ 9
       ---[ 10
              ---[ 11
------------------------------------------------
*/

//这个是Item interface{},需要导包github.com/cheekybits/genny/generic
type Item generic.Type

//节点结构体
type Node struct {
	key int //key
	value Item //value ,interface{}
	left *Node //树的左边
	right *Node //树的右边
}

//二叉搜索树结构体
type ItemBinarySearchTree struct {
	root *Node //根节点
	lock sync.RWMutex //读写锁
}


func (tree *ItemBinarySearchTree) String()  {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	fmt.Println("----------------------------------")
	stringify(tree.root,0)
	fmt.Println("----------------------------------")

}
func stringify(n *Node,level int)  {
	fmt.Println("是空？",n)
	fmt.Println("level++前：",level)
	if n!=nil{ //如果节点不为空
		format:=""//初始化打印空字符
		for i:=0;i<level;i++{//循环打印空格数，累加
			format+="      "
		}
		format+="----[ "//在前面空格后再打印---[
		/*
		level=0 ----[
		level=1      ----[
		level=2            ----[
		level=3                  ----[
		*/
		fmt.Println(format)
		level++//空格数＋１
		fmt.Println("level++后:",level)
		stringify(n.left,level)//L　递归格式化左节点
		fmt.Println(n.key,"n.left:",n.left,"level:",level)
		//如果上面递归最后为nil才执行到这行,这时level=4
		//经过上面的左边递归找到了最左边的叶子，然后下面直接打印出最左边的叶子节点
		fmt.Printf(format+"%d\n", n.key)
		//第一次递归执行到这　n.key=1，找到叶子节点１，直接打印出来
		stringify(n.right, level)
		/*先遍历第四层就是key为１的右边有没有,１右边肯定没有，所以为nil,虽然为空，但是因为
		是递归，所以不会跳出函数，会继续执行此递归后面的。
		*/
		fmt.Println(n.key,"n.right",n.right,"level:",level)//上面因为１右边没有了，所以为空，直接执行这行
		//然后决对不会执行上面的递归了，直接循环执行上面递归下面一行开始。输出left
	}
}

func (tree *ItemBinarySearchTree) Insert(key int,value Item)  {
	//上锁
	tree.lock.Lock()
	//解锁
	defer tree.lock.Unlock()
	node:=&Node{key,value,nil,nil}
	if tree.root==nil{
		tree.root=node
	}else{
		insertNode(tree.root,node)
	}
}
func insertNode(node,newNode *Node)  {
	if newNode.key <node.key{
		if node.left==nil{
			node.left=newNode
		}else{
			insertNode(node.left,newNode)
		}
	}
	if newNode.key>node.key {
		if node.right==nil{
			node.right=newNode
		}else {
			insertNode(node.right,newNode)
		}
	}
}

func main()  {
	//创建二叉搜索树对象
	var tree ItemBinarySearchTree
	//fmt.Println(tree)
	//插入第一个节点
	tree.Insert(8, "8")
	tree.Insert(4, "4")
	tree.Insert(10, "10")
	tree.Insert(2, "2")
	tree.Insert(6, "6")
	tree.Insert(1, "1")
	tree.Insert(3, "3")
	tree.Insert(5, "5")
	tree.Insert(7, "7")
	tree.Insert(9, "9")
	tree.Insert(11, "11")
	tree.String()
}
